﻿/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

using System;
using System.Collections.Generic;
using System.Text;

namespace Org.Apache.Harmony.Security.Provider.Crypto
{
    class Sha1Prng
    {
        // constants to use in expressions operating on bytes in int and long variables:
        // END_FLAGS - final bytes in words to append to message;
        //             see "ch.5.1 Padding the Message, FIPS 180-2"
        // RIGHT1    - shifts to right for left half of long
        // RIGHT2    - shifts to right for right half of long
        // LEFT      - shifts to left for bytes
        // MASK      - mask to select counter's bytes after shift to right

        private static readonly uint[] END_FLAGS = { 0x80000000, 0x800000, 0x8000, 0x80 };

        private static readonly int[] RIGHT1 = { 0, 40, 48, 56 };

        private static readonly int[] RIGHT2 = { 0, 8, 16, 24 };

        private static readonly int[] LEFT = { 0, 24, 16, 8 };

        private static readonly uint[] MASK = { 0xFFFFFFFF, 0x00FFFFFF, 0x0000FFFF, 0x000000FF };

        // HASHBYTES_TO_USE defines # of bytes returned by "computeHash(byte[])"
        // to use to form byte array returning by the "nextBytes(byte[])" method
        // Note, that this implementation uses more bytes than it is defined
        // in the above specification.
        private const int HASHBYTES_TO_USE = 20;

        // value of 16 defined in the "SECURE HASH STANDARD", FIPS PUB 180-2
        private const int FRAME_LENGTH = 16;

        // miscellaneous constants defined in this implementation:
        // COUNTER_BASE - initial value to set to "counter" before computing "nextBytes(..)";
        //                note, that the exact value is not defined in STANDARD
        // HASHCOPY_OFFSET   - offset for copy of current hash in "copies" array
        // EXTRAFRAME_OFFSET - offset for extra frame in "copies" array;
        //                     as the extra frame follows the current hash frame,
        //                     EXTRAFRAME_OFFSET is equal to length of current hash frame
        // FRAME_OFFSET      - offset for frame in "copies" array
        // MAX_BYTES - maximum # of seed bytes processing which doesn't require extra frame
        //             see (1) comments on usage of "seed" array below and
        //             (2) comments in "engineNextBytes(byte[])" method
        //
        // UNDEFINED  - three states of engine; initially its state is "UNDEFINED"
        // SET_SEED     call to "engineSetSeed"  sets up "SET_SEED" state,
        // NEXT_BYTES   call to "engineNextByte" sets up "NEXT_BYTES" state

        private const int COUNTER_BASE = 0;

        private const int HASHCOPY_OFFSET = 0;

        private const int EXTRAFRAME_OFFSET = 5;

        private const int FRAME_OFFSET = 21;

        private const int MAX_BYTES = 48;

        private enum State
        {
            Undefined = 0,
            SetSeed = 1,
            NextBytes = 2,
        }

        /**
         * offset in buffer to store current hash value
         */
        private const int HASH_OFFSET = 82;

        /**
         *  constant defined in "SECURE HASH STANDARD"
         */
        private const uint H0 = 0x67452301;
        /**
         *  constant defined in "SECURE HASH STANDARD"
         */
        private const uint H1 = 0xEFCDAB89;
        /**
         *  constant defined in "SECURE HASH STANDARD"
         */
        private const uint H2 = 0x98BADCFE;
        /**
         *  constant defined in "SECURE HASH STANDARD"
         */
        private const uint H3 = 0x10325476;
        /**
         *  constant defined in "SECURE HASH STANDARD"
         */
        private const uint H4 = 0xC3D2E1F0;

        /**
         * offset in buffer to store number of bytes in 0-15 word frame
         */
        private const int BYTES_OFFSET = 81;

        /**
         * # of bytes in H0-H4 words; <BR />
         * in this implementation # is set to 20 (in general # varies from 1 to 20)
         */
        private const int DIGEST_LENGTH = 20;


        private System.Security.Cryptography.SHA1Managed _Digest = new System.Security.Cryptography.SHA1Managed();

        // Structure of "seed" array:
        // -  0-79 - words for computing hash
        // - 80    - unused
        // - 81    - # of seed bytes in current seed frame
        // - 82-86 - 5 words, current seed hash
        private uint[] seed;

        // total length of seed bytes, including all processed
        private long seedLength;

        // Structure of "copies" array
        // -  0-4  - 5 words, copy of current seed hash
        // -  5-20 - extra 16 words frame;
        //           is used if final padding exceeds 512-bit length
        // - 21-36 - 16 word frame to store a copy of remaining bytes
        private uint[] copies;

        // ready "next" bytes; needed because words are returned
        private byte[] nextBytes;

        // index of used bytes in "nextBytes" array
        private int nextBIndex;

        // variable required according to "SECURE HASH STANDARD"
        private ulong counter;

        // contains int value corresponding to engine's current state
        private State state;

        // The "seed" array is used to compute both "current seed hash" and "next bytes".
        //
        // As the "SHA1" algorithm computes a hash of entire seed by splitting it into
        // a number of the 512-bit length frames (512 bits = 64 bytes = 16 words),
        // "current seed hash" is a hash (5 words, 20 bytes) for all previous full frames;
        // remaining bytes are stored in the 0-15 word frame of the "seed" array.
        //
        // As for calculating "next bytes",
        // both remaining bytes and "current seed hash" are used,
        // to preserve the latter for following "setSeed(..)" commands,
        // the following technique is used:
        // - upon getting "nextBytes(byte[])" invoked, single or first in row,
        //   which requires computing new hash, that is,
        //   there is no more bytes remaining from previous "next bytes" computation,
        //   remaining bytes are copied into the 21-36 word frame of the "copies" array;
        // - upon getting "setSeed(byte[])" invoked, single or first in row,
        //   remaining bytes are copied back.


        /**
         * The method generates a 160 bit hash value using
         * a 512 bit message stored in first 16 words of int[] array argument and
         * current hash value stored in five words, beginning OFFSET+1, of the array argument.
         * Computation is done according to SHA-1 algorithm.
         *
         * The resulting hash value replaces the previous hash value in the array;
         * original bits of the message are not preserved.
         *
         * No checks on argument supplied, that is,
         * a calling method is responsible for such checks.
         * In case of incorrect array passed to the method
         * either NPE or IndexOutOfBoundException gets thrown by JVM.
         *
         * @params
         *        arrW - integer array; arrW.length >= (BYTES_OFFSET+6); <BR />
         *               only first (BYTES_OFFSET+6) words are used
         */
        static void computeHash(uint[] arrW)
        {

            uint a = arrW[HASH_OFFSET];
            uint b = arrW[HASH_OFFSET + 1];
            uint c = arrW[HASH_OFFSET + 2];
            uint d = arrW[HASH_OFFSET + 3];
            uint e = arrW[HASH_OFFSET + 4];

            uint temp;

            // In this implementation the "d. For t = 0 to 79 do" loop
            // is split into four loops. The following constants:
            //     K = 5A827999   0 <= t <= 19
            //     K = 6ED9EBA1  20 <= t <= 39
            //     K = 8F1BBCDC  40 <= t <= 59
            //     K = CA62C1D6  60 <= t <= 79
            // are hex literals in the loops.

            for (int t = 16; t < 80; t++)
            {

                temp = arrW[t - 3] ^ arrW[t - 8] ^ arrW[t - 14] ^ arrW[t - 16];
                arrW[t] = (temp << 1) | (temp >> 31);
            }

            for (int t = 0; t < 20; t++)
            {

                temp = ((a << 5) | (a >> 27)) +
                       ((b & c) | ((~b) & d)) +
                       (e + arrW[t] + 0x5A827999);
                e = d;
                d = c;
                c = (b << 30) | (b >> 2);
                b = a;
                a = temp;
            }
            for (int t = 20; t < 40; t++)
            {

                temp = (((a << 5) | (a >> 27))) + (b ^ c ^ d) + (e + arrW[t] + 0x6ED9EBA1);
                e = d;
                d = c;
                c = (b << 30) | (b >> 2);
                b = a;
                a = temp;
            }
            for (int t = 40; t < 60; t++)
            {

                temp = ((a << 5) | (a >> 27)) + ((b & c) | (b & d) | (c & d)) +
                                                                 (e + arrW[t] + 0x8F1BBCDC);
                e = d;
                d = c;
                c = (b << 30) | (b >> 2);
                b = a;
                a = temp;
            }
            for (int t = 60; t < 80; t++)
            {

                temp = (((a << 5) | (a >> 27))) + (b ^ c ^ d) + (e + arrW[t] + 0xCA62C1D6);
                e = d;
                d = c;
                c = (b << 30) | (b >> 2);
                b = a;
                a = temp;
            }

            arrW[HASH_OFFSET] += a;
            arrW[HASH_OFFSET + 1] += b;
            arrW[HASH_OFFSET + 2] += c;
            arrW[HASH_OFFSET + 3] += d;
            arrW[HASH_OFFSET + 4] += e;
        }


        /**
         * The method appends new bytes to existing ones
         * within limit of a frame of 64 bytes (16 words).
         *
         * Once a length of accumulated bytes reaches the limit
         * the "computeHash(int[])" method is invoked on the array to compute updated hash,
         * and the number of bytes in the frame is set to 0.
         * Thus, after appending all bytes, the array contain only those bytes
         * that were not used in computing final hash value yet.
         *
         * No checks on arguments passed to the method, that is,
         * a calling method is responsible for such checks.
         *
         * @params
         *        intArray  - int array containing bytes to which to append;
         *                    intArray.length >= (BYTES_OFFSET+6)
         * @params
         *        byteInput - array of bytes to use for the update
         * @params
         *        from      - the offset to start in the "byteInput" array
         * @params
         *        to        - a number of the last byte in the input array to use,
         *                that is, for first byte "to"==0, for last byte "to"==input.length-1
         */
        static void updateHash(uint[] intArray, byte[] byteInput, int fromByte, int toByte)
        {

            // As intArray contains a packed bytes
            // the buffer's index is in the intArray[BYTES_OFFSET] element

            int index = (int)intArray[BYTES_OFFSET];
            int i = fromByte;
            int maxWord;
            int nBytes;

            int wordIndex = index >> 2;
            int byteIndex = index & 0x03;

            intArray[BYTES_OFFSET] = (uint)((index + toByte - fromByte + 1) & 0x3F);

            // In general case there are 3 stages :
            // - appending bytes to non-full word,
            // - writing 4 bytes into empty words,
            // - writing less than 4 bytes in last word

            if (byteIndex != 0)
            {       // appending bytes in non-full word (as if)

                for (; (i <= toByte) && (byteIndex < 4); i++)
                {
                    intArray[wordIndex] |= (uint)((byteInput[i] & 0xFF) << ((3 - byteIndex) << 3));
                    byteIndex++;
                }
                if (byteIndex == 4)
                {
                    wordIndex++;
                    if (wordIndex == 16)
                    {          // intArray is full, computing hash

                        computeHash(intArray);
                        wordIndex = 0;
                    }
                }
                if (i > toByte)
                {                 // all input bytes appended
                    return;
                }
            }

            // writing full words

            maxWord = (toByte - i + 1) >> 2;           // # of remaining full words, may be "0"
            for (int k = 0; k < maxWord; k++)
            {

                intArray[wordIndex] = (((uint)byteInput[i] & 0xFF) << 24) |
                                      (((uint)byteInput[i + 1] & 0xFF) << 16) |
                                      (((uint)byteInput[i + 2] & 0xFF) << 8) |
                                      (((uint)byteInput[i + 3] & 0xFF));
                i += 4;
                wordIndex++;

                if (wordIndex < 16)
                {     // buffer is not full yet
                    continue;
                }
                computeHash(intArray);      // buffer is full, computing hash
                wordIndex = 0;
            }

            // writing last incomplete word
            // after writing free byte positions are set to "0"s

            nBytes = toByte - i + 1;
            if (nBytes != 0)
            {

                uint w = ((uint)byteInput[i] & 0xFF) << 24;

                if (nBytes != 1)
                {
                    w |= ((uint)byteInput[i + 1] & 0xFF) << 16;
                    if (nBytes != 2)
                    {
                        w |= ((uint)byteInput[i + 2] & 0xFF) << 8;
                    }
                }
                intArray[wordIndex] = w;
            }

            return;
        }

        /*
         * The method invokes the SHA1Impl's "updateHash(..)" method
         * to update current seed frame and
         * to compute new intermediate hash value if the frame is full.
         *
         * After that it computes a length of whole seed.
         */
        private void UpdateSeed(byte[] bytes)
        {
            updateHash(seed, bytes, 0, bytes.Length - 1);
            seedLength += bytes.Length;
        }

        /**
         * Changes current seed by supplementing a seed argument to the current seed,
         * if this already set;
         * the argument is used as first seed otherwise. <BR />
         *
         * The method overrides "engineSetSeed(byte[])" in class SecureRandomSpi.
         *
         * @param
         *       seed - byte array
         * @throws
         *       NullPointerException - if null is passed to the "seed" argument
         */
        private void engineSetSeed(byte[] seed)
        {
            if (seed == null)
                throw new ArgumentNullException("seed");
            if (state == State.NextBytes)
                Array.Copy(copies, HASHCOPY_OFFSET, this.seed, HASH_OFFSET, EXTRAFRAME_OFFSET);
            state = State.SetSeed;
            if (seed.Length != 0)
                UpdateSeed(seed);
        }

        /**
         * Writes random bytes into an array supplied.
         * Bits in a byte are from left to right. <BR />
         *
         * To generate random bytes, the "expansion of source bits" method is used,
         * that is,
         * the current seed with a 64-bit counter appended is used to compute new bits.
         * The counter is incremented by 1 for each 20-byte output. <BR />
         *
         * The method overrides engineNextBytes in class SecureRandomSpi.
         *
         * @param
         *       bytes - byte array to be filled in with bytes
         * @throws
         *       NullPointerException - if null is passed to the "bytes" argument
         */
        private void engineNextBytes(byte[] bytes, int bytesOffset, int bytesLength)
        {

            int n;

            ulong bits; // number of bits required by Secure Hash Standard
            int nextByteToReturn; // index of ready bytes in "bytes" array
            uint lastWord; // index of last word in frame containing bytes
            const int extrabytes = 7;// # of bytes to add in order to computer # of 8 byte words

            if (bytes == null)
            {
                throw new ArgumentNullException("bytes");
            }

            lastWord = seed[BYTES_OFFSET] == 0 ? 0
                    : (seed[BYTES_OFFSET] + extrabytes) >> 3 - 1;

            if (state == State.Undefined)
            {

                // no seed supplied by user, hence it is generated thus randomizing internal state
                throw new NotImplementedException();
                //updateSeed(RandomBitsSupplier.getRandomBits(DIGEST_LENGTH));
                //nextBIndex = HASHBYTES_TO_USE;

            }
            else if (state == State.SetSeed)
            {

                Array.Copy(seed, HASH_OFFSET, copies, HASHCOPY_OFFSET, EXTRAFRAME_OFFSET);

                // possible cases for 64-byte frame:
                //
                // seed bytes < 48      - remaining bytes are enough for all, 8 counter bytes,
                //                        0x80, and 8 seedLength bytes; no extra frame required
                // 48 < seed bytes < 56 - remaining 9 bytes are for 0x80 and 8 counter bytes
                //                        extra frame contains only seedLength value at the end
                // seed bytes > 55      - extra frame contains both counter's bytes
                //                        at the beginning and seedLength value at the end;
                //                        note, that beginning extra bytes are not more than 8,
                //                        that is, only 2 extra words may be used

                // no need to set to "0" 3 words after "lastWord" and
                // more than two words behind frame
                for (uint i = lastWord + 3; i < FRAME_LENGTH + 2; i++)
                {
                    seed[i] = 0;
                }

                bits = ((ulong)seedLength << 3) + 64; // transforming # of bytes into # of bits

                // putting # of bits into two last words (14,15) of 16 word frame in
                // seed or copies array depending on total length after padding
                if (seed[BYTES_OFFSET] < MAX_BYTES)
                {
                    seed[14] = (uint)(bits >> 32);
                    seed[15] = (uint)(bits & 0xFFFFFFFF);
                }
                else
                {
                    copies[EXTRAFRAME_OFFSET + 14] = (uint)(bits >> 32);
                    copies[EXTRAFRAME_OFFSET + 15] = (uint)(bits & 0xFFFFFFFF);
                }

                nextBIndex = HASHBYTES_TO_USE; // skipping remaining random bits
            }
            state = State.NextBytes;

            if (bytesLength == 0)
            {
                return;
            }

            nextByteToReturn = 0;

            // possibly not all of HASHBYTES_TO_USE bytes were used previous time
            n = (HASHBYTES_TO_USE - nextBIndex) < (bytesLength - nextByteToReturn) ? HASHBYTES_TO_USE
                    - nextBIndex
                    : bytesLength - nextByteToReturn;
            if (n > 0)
            {
                Array.Copy(nextBytes, nextBIndex, bytes, nextByteToReturn + bytesOffset, n);
                nextBIndex += n;
                nextByteToReturn += n;
            }

            if (nextByteToReturn >= bytesLength)
            {
                return; // return because "bytes[]" are filled in
            }

            n = (int)(seed[BYTES_OFFSET] & 0x03);
            for (; ; )
            {
                if (n == 0)
                {

                    seed[lastWord] = (uint)(counter >> 32);
                    seed[lastWord + 1] = (uint)(counter & 0xFFFFFFFF);
                    seed[lastWord + 2] = END_FLAGS[0];

                }
                else
                {

                    seed[lastWord] |= (uint)((counter >> RIGHT1[n]) & MASK[n]);
                    seed[lastWord + 1] = (uint)((counter >> RIGHT2[n]) & 0xFFFFFFFF);
                    seed[lastWord + 2] = (uint)((counter << LEFT[n]) | END_FLAGS[n]);
                }
                if (seed[BYTES_OFFSET] > MAX_BYTES)
                {
                    copies[EXTRAFRAME_OFFSET] = seed[FRAME_LENGTH];
                    copies[EXTRAFRAME_OFFSET + 1] = seed[FRAME_LENGTH + 1];
                }

                computeHash(seed);

                if (seed[BYTES_OFFSET] > MAX_BYTES)
                {

                    Array.Copy(seed, 0, copies, FRAME_OFFSET, FRAME_LENGTH);
                    Array.Copy(copies, EXTRAFRAME_OFFSET, seed, 0, FRAME_LENGTH);

                    computeHash(seed);
                    Array.Copy(copies, FRAME_OFFSET, seed, 0, FRAME_LENGTH);
                }
                counter++;

                int j = 0;
                for (int i = 0; i < EXTRAFRAME_OFFSET; i++)
                {
                    uint k = seed[HASH_OFFSET + i];
                    nextBytes[j] = (byte)(k >> 24); // getting first  byte from left
                    nextBytes[j + 1] = (byte)(k >> 16); // getting second byte from left
                    nextBytes[j + 2] = (byte)(k >> 8); // getting third  byte from left
                    nextBytes[j + 3] = (byte)(k); // getting fourth byte from left
                    j += 4;
                }

                nextBIndex = 0;
                j = HASHBYTES_TO_USE < (bytesLength - nextByteToReturn) ? HASHBYTES_TO_USE
                        : bytesLength - nextByteToReturn;

                if (j > 0)
                {
                    Array.Copy(nextBytes, 0, bytes, nextByteToReturn + bytesOffset, j);
                    nextByteToReturn += j;
                    nextBIndex += j;
                }

                if (nextByteToReturn >= bytesLength)
                {
                    break;
                }
            }
        }

        public Sha1Prng()
        {
            seed = new uint[HASH_OFFSET + EXTRAFRAME_OFFSET];
            seed[HASH_OFFSET + 0] = H0;
            seed[HASH_OFFSET + 1] = H1;
            seed[HASH_OFFSET + 2] = H2;
            seed[HASH_OFFSET + 3] = H3;
            seed[HASH_OFFSET + 4] = H4;

            seedLength = 0;
            copies = new uint[2 * FRAME_LENGTH + EXTRAFRAME_OFFSET];
            nextBytes = new byte[DIGEST_LENGTH];
            nextBIndex = HASHBYTES_TO_USE;
            counter = COUNTER_BASE;
            state = State.Undefined;
        }

        private void DumpSeed(uint[] values)
        {
            var result = new StringBuilder();
            for (int i = 0; i != values.Length; ++i)
            {
                if (i != 0)
                    result.Append("-");
                result.AppendFormat("{0:X08}", values[i]);
            }
            Console.Out.WriteLine(result.ToString());
        }

        public void AddSeedMaterial(long seed)
        {
            AddSeedMaterial(BitConverter.GetBytes(seed));
        }

        public void AddSeedMaterial(byte[] seed)
        {
            engineSetSeed(seed);
        }

        public void NextBytes(byte[] bytes, int start, int len)
        {
            engineNextBytes(bytes, start, len);
        }

        public void NextBytes(byte[] bytes)
        {
            engineNextBytes(bytes, 0, bytes.Length);
        }
    }
}
